翻訳と辞書 Words near each other ・ Algorithmic efficiency ・ Algorithmic game theory ・ Algorithmic inference ・ Algorithmic information theory ・ Algorithmic learning theory ・ Algorithmic logic ・ Algorithmic Lovász local lemma ・ Algorithmic mechanism design ・ Algorithmic Number Theory Symposium ・ Algorithmic probability ・ Algorithmic program debugging ・ Algorithmic regulation ・ Algorithmic skeleton ・ Algorithmic state machine ・ Algorithmic trading ・ Algorithmic version for Szemerédi regularity partition ・ Algorithmica ・ Algorithmically random sequence ・ Algorithmics ・ Algorithmics Inc. ・ Algorithms (journal) ・ Algorithms + Data Structures = Programs ・ Algorithms for calculating variance ・ Algorithms for Recovery and Isolation Exploiting Semantics ・ Algorithms Unlocked ・ Algorithms-Aided Design (AAD) ・ Algorta ・ Algorta (Metro Bilbao) ・ Algorta, Uruguay ・ Algoryx Simulation AB Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Algorithmic version for Szemerédi regularity partition ： ウィキペディア英語版 Algorithmic version for Szemerédi regularity partition ''A Simple Algorithm for Constructing Szemerédi's Regularity Partition'' is a paper by Alan M. Frieze and Ravi Kannan giving an algorithmic version of the Szemerédi regularity lemma to find an ε-regular partition of a given graph. ==Formal statement of the regularity lemma== The formal statement of Szemerédi's regularity lemma requires some definitions. Let ''G'' be a graph. The ''density'' ''d''(''X'',''Y'') of a pair of disjoint vertex sets ''X'', ''Y'' is defined as ''d''(''X'',''Y'')=|''E''(''X'',''Y'')|/|''X''||''Y''| where ''E''(''X'',''Y'') denotes the set of edges having one end vertex in ''X'' and one in ''Y''. For ε>0, a pair of vertex sets ''X'' and ''Y'' is called ε-regular, if for all subsets ''A''⊆''X'' and ''B''⊆''Y'' satisfying |''A''| ≥ε |''X''| and |''B''| ≥ ε |''Y''|, we have |''d''(''X'',''Y'')-''d''(''A'',''B'')| ≤ ε. A partition of the vertex set of ''G'' into ''k'' sets, ''V''1,...,''V''''k'', is called an ''equitable'' partition if for all $i,\; j$, ||''V''''i''|-|''V''''j''||≤1. An equitable partition is an $\backslash epsilon$-''regular partition'', if for all but at most $\backslash epsilon$ pairs (''i'',''j'') the pair $(V\_i,\; V\_j,)$ is $\backslash epsilon$-regular. Now we are ready to state the regularity lemma. Regularity lemma. For every $\backslash epsilon\; >\; 0$ and positive integer $m$ there exist integers $N$ and $M$ such that if $G$ is a graph with at least $N$ vertices, there exists an integer $k$ in the range $m$ ≤ $k$ ≤ $M$ and an $\backslash epsilon$-regular partition of the vertex set of $G$ into $k$ sets. It is a common variant in the definition of an $\backslash epsilon$-regular partition to require that the vertex sets all have the same size, while collecting the leftover vertices in an "error"-set $V\_0$ whose size is at most an $\backslash epsilon$-fraction of the size of the vertex set of $G$. Szemerédi's regularity lemma is one of the most powerful tools of extremal graph theory. It says that, in some sense, all graphs can be approximated by random-looking graphs. Therefore the lemma helps in proving theorems for arbitrary graphs whenever the corresponding result is easy for random graphs. The first constructive version was provided by Alon, Duke, Leffman, Rödl and Yuster.〔 〕 Subsequently Frieze and Kannan gave a different version and extended it to hypergraphs.〔 〕 The paper 〔.〕 is a nice survey on regularity lemma and its various applications. Here we will briefly describe a different construction due to Alan Frieze and Ravi Kannan that uses singular values of matrices. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Algorithmic version for Szemerédi regularity partition」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.